{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #宝石补给"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #simulation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #模拟"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: giveGem"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #宝石补给"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "欢迎各位勇者来到力扣新手村，在开始试炼之前，请各位勇者先进行「宝石补给」。\n",
    "\n",
    "每位勇者初始都拥有一些能量宝石， `gem[i]` 表示第 `i` 位勇者的宝石数量。现在这些勇者们进行了一系列的赠送，`operations[j] = [x, y]` 表示在第 `j` 次的赠送中 第 `x` 位勇者将自己一半的宝石（需向下取整）赠送给第 `y` 位勇者。\n",
    "\n",
    "在完成所有的赠送后，请找到拥有**最多**宝石的勇者和拥有**最少**宝石的勇者，并返回他们二者的宝石数量**之差**。\n",
    "\n",
    "**注意：**\n",
    "- 赠送将按顺序逐步进行。\n",
    "\n",
    "**示例 1：**\n",
    ">输入：`gem = [3,1,2], operations = [[0,2],[2,1],[2,0]]`\n",
    ">\n",
    ">输出：`2`\n",
    ">\n",
    ">解释：\n",
    ">第 1 次操作，勇者 `0` 将一半的宝石赠送给勇者 `2`， `gem = [2,1,3]`\n",
    ">第 2 次操作，勇者 `2` 将一半的宝石赠送给勇者 `1`， `gem = [2,2,2]`\n",
    ">第 3 次操作，勇者 `2` 将一半的宝石赠送给勇者 `0`， `gem = [3,2,1]`\n",
    ">返回 3 - 1 = 2\n",
    "\n",
    "**示例 2：**\n",
    ">输入：`gem = [100,0,50,100], operations = [[0,2],[0,1],[3,0],[3,0]]`\n",
    ">\n",
    ">输出：`75`\n",
    ">\n",
    ">解释：\n",
    ">第 1 次操作，勇者 `0` 将一半的宝石赠送给勇者 `2`， `gem = [50,0,100,100]`\n",
    ">第 2 次操作，勇者 `0` 将一半的宝石赠送给勇者 `1`， `gem = [25,25,100,100]`\n",
    ">第 3 次操作，勇者 `3` 将一半的宝石赠送给勇者 `0`， `gem = [75,25,100,50]`\n",
    ">第 4 次操作，勇者 `3` 将一半的宝石赠送给勇者 `0`， `gem = [100,25,100,25]`\n",
    ">返回 100 - 25 = 75\n",
    "\n",
    "**示例 3：**\n",
    ">输入：`gem = [0,0,0,0], operations = [[1,2],[3,1],[1,2]]`\n",
    ">\n",
    ">输出：`0`\n",
    "\n",
    "**提示：**\n",
    "- `2 <= gem.length <= 10^3`\n",
    "- `0 <= gem[i] <= 10^3`\n",
    "- `0 <= operations.length <= 10^4`\n",
    "- `operations[i].length == 2`\n",
    "- `0 <= operations[i][0], operations[i][1] < gem.length`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [WHnhjV](https://leetcode.cn/problems/WHnhjV/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [WHnhjV](https://leetcode.cn/problems/WHnhjV/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[3,1,2]\\n[[0,2],[2,1],[2,0]]', '[100,0,50,100]\\n[[0,2],[0,1],[3,0],[3,0]]', '[0,0,0,0]\\n[[1,2],[3,1],[1,2]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def giveGem(self, gem: List[int], operations: List[List[int]]) -> int:\n",
    "        while operations:\n",
    "            i, j = operations.pop(0)\n",
    "            # num = copy.deepcopy(gem[i]) // 2\n",
    "            # gem[i] = gem[i] - num\n",
    "            # gem[j] = gem[j] + num\n",
    "            gem[j] += gem[i] // 2\n",
    "            gem[i] -= gem[i] // 2\n",
    "            \n",
    "        result = max(gem)-min(gem)\n",
    "        return result\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def giveGem(self, gem: List[int], operations: List[List[int]]) -> int:\n",
    "        res=0\n",
    "        temp=0\n",
    "        for item in operations:\n",
    "            temp = gem[item[0]]//2\n",
    "            gem[item[0]]-=temp\n",
    "            gem[item[1]]+=temp\n",
    "        return max(gem)-min(gem)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def giveGem(self, gem: List[int], operations: List[List[int]]) -> int:\n",
    "        for x, y in operations:\n",
    "            v = gem[x] >>1\n",
    "            gem[y] += v\n",
    "            gem[x] -= v\n",
    "        return max(gem) - min(gem)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def giveGem(self, gem: List[int], operations: List[List[int]]) -> int:\n",
    "        while operations:\n",
    "            i, j = operations.pop(0)\n",
    "            # num = copy.deepcopy(gem[i]) // 2\n",
    "            # gem[i] = gem[i] - num\n",
    "            # gem[j] = gem[j] + num\n",
    "            gem[j] += gem[i] // 2\n",
    "            gem[i] -= gem[i] // 2\n",
    "            \n",
    "        result = max(gem)-min(gem)\n",
    "        return result\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def giveGem(self, gem: List[int], operations: List[List[int]]) -> int:\n",
    "        for x,y in operations:\n",
    "            temp = gem[x]//2\n",
    "            gem[y] += temp\n",
    "            gem[x] -= temp\n",
    "        return max(gem) - min(gem)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def giveGem(self, gem: List[int], operations: List[List[int]]) -> int:\n",
    "        for op in operations:\n",
    "            i, j = op[0], op[1]\n",
    "            gem[j] += gem[i] // 2\n",
    "            gem[i] -= gem[i] // 2\n",
    "           \n",
    "\n",
    "        return max(gem) - min(gem)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def giveGem(self, gem: List[int], operations: List[List[int]]) -> int:\n",
    "        for opt in operations:\n",
    "            num = gem[opt[0]] // 2\n",
    "            gem[opt[0]] -= num\n",
    "            gem[opt[1]] += num\n",
    "        return max(gem) - min(gem)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def giveGem(self, gem: List[int], operations: List[List[int]]) -> int:\n",
    "\n",
    "        while operations:\n",
    "            i, j = operations.pop(0)\n",
    "            num = copy.deepcopy(gem[i]) // 2\n",
    "            gem[i] = gem[i] - num\n",
    "            gem[j] = gem[j] + num\n",
    "        \n",
    "        gem = sorted(gem)\n",
    "        return gem[-1] - gem[0]\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def giveGem(self, gem: List[int], operations: List[List[int]]) -> int:\n",
    "        for op in operations:\n",
    "            t = gem[op[0]] // 2\n",
    "            gem[op[0]] -= t\n",
    "            gem[op[1]] += t\n",
    "        return max(gem) - min(gem)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def giveGem(self, gem: List[int], operations: List[List[int]]) -> int:\n",
    "        for i, j in operations:\n",
    "            tmp = gem[i] // 2\n",
    "            gem[i] -= tmp\n",
    "            gem[j] += tmp\n",
    "        return max(gem) - min(gem)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def giveGem(self, gem: List[int], operations: List[List[int]]) -> int:\n",
    "        for x, y in operations:\n",
    "            temp = gem[x] // 2\n",
    "            gem[x] -= temp\n",
    "            gem[y] += temp\n",
    "        return max(gem) - min(gem)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def giveGem(self, gem: List[int], operations: List[List[int]]) -> int:\n",
    "        for x,y in operations:\n",
    "            number = gem[x] // 2    # 要交换的宝石数量\n",
    "\n",
    "            gem[x] -= number\n",
    "            gem[y] += number\n",
    "        \n",
    "        # mn, mx = gem[0], gem[0]\n",
    "\n",
    "        # for num in gem:\n",
    "        #     mn = min(mn, num)\n",
    "        #     mx = max(mx, num)\n",
    "\n",
    "        return max(gem)-min(gem)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def giveGem(self, gem: List[int], operations: List[List[int]]) -> int:\n",
    "        for x, y in operations:\n",
    "            g = gem[x] // 2\n",
    "            gem[x] -= g\n",
    "            gem[y] += g\n",
    "        return max(gem) - min(gem)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def giveGem(self, gem: List[int], operations: List[List[int]]) -> int:\n",
    "        for x,y in operations:\n",
    "            n = gem[x]//2\n",
    "            gem[x]-=n\n",
    "            gem[y]+=n\n",
    "        MAX,MIN=0,10**4\n",
    "        for i in range(len(gem)):\n",
    "            MAX=max(MAX,gem[i])\n",
    "            MIN=min(MIN,gem[i])\n",
    "        return MAX-MIN"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def giveGem(self, gem: List[int], operations: List[List[int]]) -> int:\n",
    "        for x, y in operations:\n",
    "            num = gem[x] // 2\n",
    "            gem[x] -= num\n",
    "            gem[y] += num\n",
    "        return max(gem) - min(gem)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def giveGem(self, gem: List[int], operations: List[List[int]]) -> int:\n",
    "        result = 0\n",
    "        while operations:\n",
    "            i, j = operations.pop(0)\n",
    "            num = copy.deepcopy(gem[i]) // 2\n",
    "            gem[i] = gem[i] - num\n",
    "            gem[j] = gem[j] + num\n",
    "            result = max(gem)-min(gem)\n",
    "        \n",
    "        return result\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def giveGem(self, gem: List[int], operations: List[List[int]]) -> int:\n",
    "        for j in range(len(operations)):\n",
    "            m = operations[j][0]\n",
    "            n = operations[j][1]\n",
    "            amount = gem[m]//2\n",
    "            gem[m] = gem[m] - amount\n",
    "            gem[n] = gem[n] + amount\n",
    "        \n",
    "        return max(gem)-min(gem)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def giveGem(self, gem: List[int], operations: List[List[int]]) -> int:\n",
    "        for i, j in operations:\n",
    "            s = gem[i] // 2\n",
    "            gem[i] -= s\n",
    "            gem[j] += s\n",
    "        return max(gem) - min(gem)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def giveGem(self, gem: List[int], operations: List[List[int]]) -> int:\n",
    "        for start, end in operations:\n",
    "            gem[start], gem[end] = (gem[start] + 1) // 2, gem[end] + gem[start] // 2\n",
    "        return max(gem) - min(gem)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def giveGem(self, gem: List[int], operations: List[List[int]]) -> int:\n",
    "        for operation in operations:\n",
    "            gem[operation[1]]+=gem[operation[0]]//2\n",
    "            gem[operation[0]]=gem[operation[0]]-gem[operation[0]]//2\n",
    "        return max(gem)-min(gem)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def giveGem(self, gem: List[int], operations: List[List[int]]) -> int:\n",
    "        for op in operations:\n",
    "            x = gem[op[0]]//2\n",
    "            gem[op[0]] -= x\n",
    "            gem[op[1]] += x\n",
    "        return max(gem)-min(gem)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def giveGem(self, gem: List[int], operations: List[List[int]]) -> int:\n",
    "        for op in operations:\n",
    "            fr, to = op\n",
    "            give = gem[fr] // 2\n",
    "            gem[fr] -= give\n",
    "            gem[to] += give\n",
    "        \n",
    "        return max(gem) - min(gem)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def giveGem(self, gem: List[int], operations: List[List[int]]) -> int:\n",
    "        for i in range(len(operations)):\n",
    "            temp=gem[operations[i][0]]//2\n",
    "            gem[operations[i][1]]+=temp\n",
    "            gem[operations[i][0]] = gem[operations[i][0]]-temp\n",
    "            # print(gem)\n",
    "        gem.sort()\n",
    "        return gem[-1]-gem[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def giveGem(self, gem: List[int], operations: List[List[int]]) -> int:\n",
    "        for op in operations:\n",
    "            x = gem[op[0]] // 2\n",
    "            gem[op[0]] -= x\n",
    "            gem[op[1]] += x\n",
    "        return max(gem) - min(gem)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def giveGem(self, gem: List[int], operations: List[List[int]]) -> int:\n",
    "        for i in operations:\n",
    "            tmp = gem[i[0]] // 2\n",
    "            gem[i[0]] -= tmp\n",
    "            gem[i[1]] += tmp\n",
    "        return max(gem) - min(gem)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def giveGem(self, gem: List[int], operations: List[List[int]]) -> int:\n",
    "        for x,y in operations:\n",
    "            give=gem[x]>>1 \n",
    "            gem[x]-=give\n",
    "            gem[y]+=give\n",
    "        return max(gem)-min(gem)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def giveGem(self, gem: List[int], operations: List[List[int]]) -> int:\n",
    "        for item in operations:\n",
    "            x=gem[item[0]]//2\n",
    "            gem[item[0]]-=x\n",
    "            gem[item[1]]+=x\n",
    "        return max(gem)-min(gem)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def giveGem(self, gem: List[int], operations: List[List[int]]) -> int:\n",
    "        for o in operations:\n",
    "            gem[o[1]] += int(gem[o[0]]/2)\n",
    "            gem[o[0]] -= int(gem[o[0]]/2)\n",
    "        gem.sort()\n",
    "        leng = len(gem)\n",
    "        res = gem[leng-1]-gem[0]\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def giveGem(self, gem: List[int], operations: List[List[int]]) -> int:\n",
    "        for var in operations:\n",
    "            num = gem[var[0]]//2\n",
    "            gem[var[1]] += num\n",
    "            gem[var[0]] -= num\n",
    "            \n",
    "        return max(gem) - min(gem)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def giveGem(self, gem: List[int], operations: List[List[int]]) -> int:\n",
    "\n",
    "        for i in operations:\n",
    "            tmp = floor(gem[i[0]] / 2)\n",
    "            gem[i[0]] -= tmp\n",
    "            gem[i[1]] += tmp\n",
    "        return max(gem) - min(gem)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def giveGem(self, gem: List[int], operations: List[List[int]]) -> int:\n",
    "        for giv in operations:\n",
    "            gem[giv[1]]=gem[giv[1]]+gem[giv[0]]//2\n",
    "            gem[giv[0]]=gem[giv[0]]-gem[giv[0]]//2\n",
    "            \n",
    "            # print(gem)\n",
    "        return max(gem)-min(gem)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def giveGem(self, gem: List[int], operations: List[List[int]]) -> int:\n",
    "        for x, y in operations:\n",
    "            v = gem[x] >> 1\n",
    "            gem[y] += v\n",
    "            gem[x] -= v\n",
    "        return max(gem) - min(gem)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def giveGem(self, gem: List[int], operations: List[List[int]]) -> int:\n",
    "        for i,j in operations:\n",
    "            gem[j] += gem[i]//2\n",
    "            gem[i] -= gem[i]//2\n",
    "            \n",
    "        return max(gem)-min(gem)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def giveGem(self, gem: List[int], operations: List[List[int]]) -> int:\n",
    "        for op in operations:\n",
    "            tmp = gem[op[0]]\n",
    "            gem[op[0]] -= int(tmp/2)\n",
    "            gem[op[1]] += int(tmp/2)\n",
    "        return max(gem) - min(gem)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def giveGem(self, gem: List[int], operations: List[List[int]]) -> int:\n",
    "        for var in operations:\n",
    "            num = gem[var[0]]//2\n",
    "            gem[var[1]] += num\n",
    "            gem[var[0]] -= num\n",
    "            \n",
    "        return max(gem) - min(gem)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def giveGem(self, gem: List[int], operations: List[List[int]]) -> int:\n",
    "        for x, y in operations:\n",
    "            v = gem[x] >> 1\n",
    "            gem[y] += v\n",
    "            gem[x] -= v\n",
    "        return max(gem) - min(gem)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def giveGem(self, gem: List[int], operations: List[List[int]]) -> int:\n",
    "        for x,y in operations:\n",
    "            gem[y] += gem[x] // 2\n",
    "            gem[x] -= gem[x] // 2\n",
    "            #print(gem)\n",
    "\n",
    "        return max(gem) - min(gem)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def giveGem(self, gem: List[int], operations: List[List[int]]) -> int:\n",
    "        for i in operations:\n",
    "            t = (gem[i[0]] // 2)\n",
    "            gem[i[0]], gem[i[1]] = gem[i[0]] - t ,  gem[i[1]] + t\n",
    "        return max(gem) - min(gem)           "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def giveGem(self, gem: List[int], operations: List[List[int]]) -> int:\n",
    "        for x, y in operations:\n",
    "            number = gem[x] // 2\n",
    "            gem[x] -= number\n",
    "            gem[y] += number\n",
    "        mn, mx = gem[0], gem[0]\n",
    "        for number in gem:\n",
    "            mn = min(number, mn)\n",
    "            mx = max(number, mx)\n",
    "        return mx - mn\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def giveGem(self, gem: List[int], operations: List[List[int]]) -> int:\n",
    "\n",
    "        for v in operations:\n",
    "            # print([v[0],v[1]])\n",
    "            gem[v[1]] = round(gem[v[0]]//2, 1) + gem[v[1]]\n",
    "            gem[v[0]] = gem[v[0]]-round(gem[v[0]]//2, 1)\n",
    "    \n",
    "        return max(gem)-min(gem)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def giveGem(self, gem: List[int], operations: List[List[int]]) -> int:\n",
    "        for x,y in operations:\n",
    "            a = gem[x] // 2\n",
    "            gem[x] -= a\n",
    "            gem[y] += a\n",
    "        m = max(gem)\n",
    "        n = min(gem)\n",
    "        return m - n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def giveGem(self, gem: List[int], operations: List[List[int]]) -> int:\n",
    "        for step in operations:\n",
    "            give = gem[step[0]] // 2\n",
    "            gem[step[0]] -= give\n",
    "            gem[step[1]] += give\n",
    "        return max(gem) - min(gem)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def giveGem(self, gem: List[int], operations: List[List[int]]) -> int:\n",
    "        for op in operations:\n",
    "            v = gem[op[0]] // 2\n",
    "            gem[op[0]] -= v\n",
    "            gem[op[1]] += v\n",
    "        return max(gem) - min(gem)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def giveGem(self, gem: List[int], operations: List[List[int]]) -> int:\n",
    "        n=len(operations)\n",
    "\n",
    "        for op in operations:\n",
    "            i=op[0]\n",
    "            j=op[1]\n",
    "            diff=gem[i]//2\n",
    "            # 这里得用 diff，如果用 gem[j]=gem[j]+gem[i]//2 j的值不对\n",
    "            gem[i]=gem[i]-diff\n",
    "            gem[j]=gem[j]+diff\n",
    "            # print(gem[i],gem[j])\n",
    "            # print(gem)\n",
    "        return max(gem)-min(gem)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def giveGem(self, gem: List[int], operations: List[List[int]]) -> int:\n",
    "        for x,y in operations:\n",
    "            operate_num = gem[x] // 2\n",
    "            gem[x] -= operate_num\n",
    "            gem[y] += operate_num\n",
    "        \n",
    "        return max(gem)-min(gem)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def giveGem(self, gem: List[int], operations: List[List[int]]) -> int:\n",
    "        for i,j in operations:\n",
    "            t = (gem[i] // 2)\n",
    "            gem[i], gem[j] = gem[i] - t ,  gem[j] + t\n",
    "        return max(gem) - min(gem)           "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def giveGem(self, gem: List[int], operations: List[List[int]]) -> int:\n",
    "        for op in operations:\n",
    "            df = gem[op[0]]//2\n",
    "            gem[op[0]] -= df\n",
    "            gem[op[1]] += df\n",
    "        gem.sort()\n",
    "        return gem[-1] - gem[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def giveGem(self, gem: List[int], operations: List[List[int]]) -> int:\n",
    "        for i in operations:\n",
    "            t = gem[i[0]] // 2\n",
    "            gem[i[0]] -= t\n",
    "            gem[i[1]] += t\n",
    "        gem.sort()\n",
    "        return gem[-1] - gem[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def giveGem(self, gem: List[int], operations: List[List[int]]) -> int:\n",
    "        for exchange in operations:\n",
    "            give = exchange[0]\n",
    "            take = exchange[1]\n",
    "            gemtrade = gem[give] // 2\n",
    "            gem[give] -= gemtrade\n",
    "            gem[take] += gemtrade\n",
    "        return max(gem) - min (gem)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def giveGem(self, gem: List[int], operations: List[List[int]]) -> int:\n",
    "        for x,y in operations:\n",
    "            gem[y] += int(gem[x] / 2)\n",
    "            gem[x] -= int(gem[x] / 2)\n",
    "        return max(gem) - min(gem)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def giveGem(self, gem: List[int], operations: List[List[int]]) -> int:\n",
    "        for v in operations:\n",
    "            temp = int(gem[v[0]]/2)\n",
    "            gem[v[0]] = gem[v[0]]-temp\n",
    "            gem[v[1]] = gem[v[1]]+temp\n",
    "        return max(gem)-min(gem)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def giveGem(self, gem: List[int], operations: List[List[int]]) -> int:\n",
    "        for j in range(len(operations)):\n",
    "            x = operations[j][0]\n",
    "            y = operations[j][1]\n",
    "            gem[y] += gem[x]//2\n",
    "            gem[x] -= gem[x]//2\n",
    "        return max(gem)-min(gem)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def giveGem(self, gem: List[int], operations: List[List[int]]) -> int:\n",
    "        ans=0\n",
    "        i=0\n",
    "        i=int(i)\n",
    "        for i in range (0,len(operations)):\n",
    "            \n",
    "\n",
    "                a=operations[i][0]\n",
    "                c=operations[i][1]\n",
    "      \n",
    "                d=gem[a]//2\n",
    "                gem[a]=gem[a]-d\n",
    "                gem[c]=gem[c]+d\n",
    "        \n",
    "        ans=max(gem)-min(gem)\n",
    "        return ans\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def giveGem(self, gem: List[int], operations: List[List[int]]) -> int:\n",
    "        for x,y in operations:\n",
    "            v= gem[x] >>1\n",
    "            gem[y] += v\n",
    "            gem[x] -= v\n",
    "        return max(gem)- min(gem)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def giveGem(self, gem: List[int], operations: List[List[int]]) -> int:\n",
    "        for  i in operations:\n",
    "            m = gem[i[0]] // 2\n",
    "            gem[i[0]] -= m\n",
    "            gem[i[1]] += m\n",
    "        return max(gem) - min(gem)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def giveGem(self, gem: List[int], operations: List[List[int]]) -> int:\n",
    "        for x, y in operations:\n",
    "            number = gem[x] // 2\n",
    "            gem[x] -= number\n",
    "            gem[y] += number\n",
    "        mn, mx = gem[0], gem[0]\n",
    "        for number in gem:\n",
    "            mn = min(number, mn)\n",
    "            mx = max(number, mx)\n",
    "        return mx - mn\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def giveGem(self, gem: List[int], operations: List[List[int]]) -> int:\n",
    "        for x,y in operations:\n",
    "            gem[y] += gem[x] >> 1\n",
    "            gem[x] -= gem[x] >> 1\n",
    "        return max(gem) - min(gem)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def giveGem(self, gem: List[int], operations: List[List[int]]) -> int:\n",
    "        for x, y in operations:\n",
    "            number = gem[x] // 2\n",
    "            gem[x] -= number\n",
    "            gem[y] += number\n",
    "        mn, mx = gem[0], gem[0]\n",
    "        for number in gem:\n",
    "            mn = min(number, mn)\n",
    "            mx = max(number, mx)\n",
    "        return mx - mn"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def giveGem(self, gem: List[int], operations: List[List[int]]) -> int:\n",
    "        for i in operations:\n",
    "            gem[i[1]] += (gem[i[0]] // 2)\n",
    "            gem[i[0]] -= (gem[i[0]] // 2)\n",
    "        return max(gem) - min(gem)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def giveGem(self, gem: List[int], operations: List[List[int]]) -> int:\n",
    "        for j in range(len(operations)):\n",
    "            gem[operations[j][1]] += gem[operations[j][0]] // 2\n",
    "            gem[operations[j][0]] -= gem[operations[j][0]] // 2 \n",
    "        print(gem)\n",
    "        return(max(gem)-min(gem))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def giveGem(self, gem: List[int], operations: List[List[int]]) -> int:\n",
    "        for i, j in operations:\n",
    "            gem[i], gem[j] = gem[i] - (gem[i]//2), gem[j] + (gem[i]//2)\n",
    "        return max(gem) - min(gem)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def giveGem(self, gem: List[int], operations: List[List[int]]) -> int:\n",
    "        for i in operations:\n",
    "            t = gem[i[0]]//2\n",
    "            gem[i[0]] = gem[i[0]] - t\n",
    "            gem[i[1]] = gem[i[1]] + t\n",
    "        nmax = max(gem)\n",
    "        nmin = min(gem)\n",
    "        return nmax - nmin"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def giveGem(self, gem: List[int], operations: List[List[int]]) -> int:\n",
    "        for x,y in operations:\n",
    "            a = gem[x] // 2\n",
    "            gem[x] -= a\n",
    "            gem[y] += a \n",
    "        mn,mx = gem[0],gem[0]\n",
    "        for i in gem:\n",
    "            mn = min(mn,i)\n",
    "            mx = max(mx,i)\n",
    "        return mx-mn"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def giveGem(self, gem: List[int], operations: List[List[int]]) -> int:\n",
    "        for o in operations:\n",
    "            value = gem[o[0]]//2\n",
    "            gem[o[0]] -= value\n",
    "            gem[o[1]] += value\n",
    "        min_value = gem[0]\n",
    "        max_value = gem[0]\n",
    "        for g in gem:\n",
    "            min_value = min(min_value, g)\n",
    "            max_value = max(max_value, g)\n",
    "        return max_value - min_value"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def giveGem(self, gem: List[int], operations: List[List[int]]) -> int:\n",
    "        for x,y in operations:\n",
    "            tmp = gem[x]//2\n",
    "            gem[x]-=tmp\n",
    "            gem[y]+=tmp\n",
    "        mn,mx=gem[0],gem[0]\n",
    "        for i in gem:\n",
    "            mn=i if i<mn else mn\n",
    "            mx=i if i>mx else mx\n",
    "        return mx-mn\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def giveGem(self, gem: List[int], operations: List[List[int]]) -> int:\n",
    "        for i in range(len(operations)):\n",
    "            from_ = operations[i][0]\n",
    "            to = operations[i][1]\n",
    "            give = gem[from_] // 2\n",
    "            gem[from_] -= give\n",
    "            gem[to] += give\n",
    "        return max(gem) - min(gem)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def giveGem(self, gem: List[int], operations: List[List[int]]) -> int:\n",
    "        for x, y in operations:\n",
    "            number = gem[x] // 2\n",
    "            gem[x] -= number\n",
    "            gem[y] += number\n",
    "        mn, mx = gem[0], gem[0]\n",
    "        for number in gem:\n",
    "            mn = min(number, mn)\n",
    "            mx = max(number, mx)\n",
    "        return mx - mn"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
